//输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 
//
// 
//
// 示例: 
//给定如下二叉树，以及目标和 target = 22， 
//
// 
//              5
//             / \
//            4   8
//           /   / \
//          11  13  4
//         /  \    / \
//        7    2  5   1
// 
//
// 返回: 
//
// 
//[
//   [5,4,11,2],
//   [5,8,4,5]
//]
// 
//
// 
//
// 提示： 
//
// 
// 节点总数 <= 10000 
// 
//
// 注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/ 
// Related Topics 树 深度优先搜索 回溯 二叉树 👍 226 👎 0


package leetcode.editor.cn1;

import com.leetcode.entity.TreeNode;

import java.util.ArrayList;
import java.util.Enumeration;
import java.util.List;
import java.util.Stack;

//Java：二叉树中和为某一值的路径
public class ErChaShuZhongHeWeiMouYiZhiDeLuJingLcof {
    public static void main(String[] args) {
        Solution solution = new ErChaShuZhongHeWeiMouYiZhiDeLuJingLcof().new Solution();
        // TO TEST
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);

        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);

        List<List<Integer>> list = solution.pathSum(root, 22);
        for (List<Integer> integers : list) {
            StringBuilder sb = new StringBuilder("");
            for (Integer integer : integers) {
                sb.append(integer + ",");
            }
            System.out.println(sb.toString());
        }
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            // 前序遍历
            List<List<Integer>> list = new ArrayList<>();
            Stack<Integer> stack = new Stack<>();
            dsf(root, target, stack, list);
            return list;
        }

        public void dsf(TreeNode node, int target, Stack<Integer> stack, List<List<Integer>> list) {
            if (node == null)
                return;
            // 叶子节点
            if (node.left == null && node.right == null && node.val == target) {
                List<Integer> list1 = new ArrayList<>();
                Enumeration<Integer> elements = stack.elements();
                while (elements.hasMoreElements()) {
                    list1.add(elements.nextElement());
                }
                list1.add(node.val);
                if (!list1.isEmpty()) {
                    list.add(list1);
                }
            } else {
                stack.push(node.val);
                dsf(node.left, target - node.val, stack, list);
                dsf(node.right, target - node.val, stack, list);
                stack.pop();
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
